МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
кафедра захисту інформації
З В І Т
до лабораторної роботи №4
з курсу: “Алгоритмічні основи криптології ”
на тему: “Алгоритми факторизації складених чисел”
Варіант № 25
1. Мета роботи.
2. Повний текст завдання.
3. Блок-схема алгоритму.
4. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення.
5. Остаточно відлагоджений текст програми згідно з отриманим завданням .
6. Результати виконання програми.
1. Мета роботи
Вивчити основні алгоритми факторизації складних чисел.
2. Завдання
Реалізувати програму, що дозволяє знаходити розкладання на множники заданого числа n комбінованим методом: р-Полларда і пробних ділень;
3. Блок-схема алгоритму
randomNumber(int n)
factorise(int n)
check(int secondDiv)
SCD(int firstNumber, int secondNumber)
button1_Click(object sender, EventArgs e)
4. Cписок ідентифікаторів констант, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення.
massDiv – масив типу int, що приймає значення дільників;
j, x, oldx, d – змінні типу int, що використовуються у методі р-Полларда;
n — змінна, що факторизується;
correction — змінна, що відповідає за точність результату;
randomNumber()– метод, що генерує випадкове число;
check()– метод логічного типу, що повертає відповідне значеня в залежності від числа;
factorise ()– метод р-Полларда факторизації складного числа;
SCD ()– метод, що повертає найменше спільне кратне двох чисел;
Form1_Load ()– метод, що виконується безпосередньо післа завантаження програми;
button1_Click () – метод, який виконує моделацію натиску на програмну кнопку;
5. Текст програми
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace k2_s2_lab4
{
public partial class Form1 : Form
{
public static List<int> massDiv = new List<int>();
public static int massDivLength;
public static int j, x, oldx, d, n;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int temp;
textBox2.Text = "";
try { n = Convert.ToInt32(textBox1.Text); }
catch (Exception) { textBox2.Text = " Avaible range 3<number<2147000598; "; return; }
if (n < 3) { textBox2.Text = " Avaible range 3<number<2147000598; "; return; }
factorise(n);
int secondDiv = n / d;
textBox2.Text += d;
while (true)
{
if (check(secondDiv) == true)
{
textBox2.Text += " * " + SCD(secondDiv, secondDiv);
temp = secondDiv / SCD(secondDiv, secondDiv);
if (check(temp) == false) { textBox2.Text += " * " + temp; break; }
else { secondDiv = temp; }
}
else { textBox2.Text += " * " + secondDiv; break; }
}
}
private bool check(int secondDiv)
{
for (int i = 0; i < massDivLength; i++)
{
if (secondDiv == massDiv[i]) break;
if (secondDiv % massDiv[i] == 0) { return true; }
}
return false;
}
private int factorise(int n)
{
d = 1;
j = 1;
if (check(n) == false) { textBox2.Text = "Number " + n + " is prime -> "; return 0; }
x = RandomNumber(n-1);
while (true)
{
oldx = x;
for (int i = 1; i < j; i++)
{
x = ((x * x) + 1) % n;
d = SCD(Math.Abs(x - oldx), n);
if (d > 1 && d < n) { return d; }
}
j *= 2;
}
...
